home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Graphics⁄Sound / RTrace-1.0-src / csg_3.c < prev    next >
Text File  |  1992-09-17  |  13KB  |  407 lines
  1. /*
  2.  * Copyright (c) 1988, 1992 Antonio Costa, INESC-Norte.
  3.  * All rights reserved.
  4.  *
  5.  * This code received contributions from the following people:
  6.  *
  7.  *  Roman Kuchkuda      - basic ray tracer
  8.  *  Mark VandeWettering - MTV ray tracer
  9.  *  Augusto Sousa       - overall, shading model
  10.  *  Craig Kolb          - CSG
  11.  *
  12.  * Redistribution and use in source and binary forms are permitted
  13.  * provided that the above copyright notice and this paragraph are
  14.  * duplicated in all such forms and that any documentation,
  15.  * advertising materials, and other materials related to such
  16.  * distribution and use acknowledge that the software was developed
  17.  * by Antonio Costa, at INESC-Norte. The name of the author and
  18.  * INESC-Norte may not be used to endorse or promote products derived
  19.  * from this software without specific prior written permission.
  20.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  21.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  22.  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  23.  */
  24. #include "defs.h"
  25. #include "extern.h"
  26. #include "csg.h"
  27.  
  28. /**********************************************************************
  29.  *    RAY TRACING - CSG - Version 7.3.1                               *
  30.  *                                                                    *
  31.  *    MADE BY    : Antonio Costa, INESC-Norte, June 1992              *
  32.  *    MODIFIED BY: Antonio Costa, INESC-Norte, July 1992              *
  33.  **********************************************************************/
  34.  
  35. /***** CSG *****/
  36. #define CSG_NODES_MAX (224)
  37.  
  38. extern tree_struct tree;
  39. extern hit_struct hit_global;
  40.  
  41. static void
  42. csg_remove(rem_object, csg_removed, non_csg_removed)
  43.   object_ptr      rem_object;
  44.   int            *csg_removed, *non_csg_removed;
  45. {
  46.   csg_ptr         csg;
  47.   texture_ptr     texture, old_texture;
  48.  
  49.   if (rem_object == NULL)
  50.     return;
  51.   FREE(rem_object->min);
  52.   FREE(rem_object->max);
  53.   if (rem_object->transf != NULL)
  54.     FREE(rem_object->transf);
  55.   if (rem_object->inv_transf != NULL)
  56.     FREE(rem_object->inv_transf);
  57.   texture = rem_object->texture;
  58.   while (texture != NULL)
  59.   {
  60.     if (texture->transf != NULL)
  61.       FREE(texture->transf);
  62.     if (texture->data != NULL)
  63.       FREE(texture->data);
  64.     old_texture = texture;
  65.     texture = texture->next;
  66.     FREE(old_texture);
  67.   }
  68.   if (rem_object->object_type != CSG_TYPE)
  69.   {
  70.     FREE(rem_object->data);
  71.     FREE(rem_object);
  72.     POSINC(*non_csg_removed);
  73.     return;
  74.   }
  75.   csg = (csg_ptr) rem_object->data;
  76.   if (csg->position != NULL)
  77.     FREE(csg->position);
  78.   texture = csg->texture;
  79.   while (texture != NULL)
  80.   {
  81.     if (texture->transf != NULL)
  82.       FREE(texture->transf);
  83.     if (texture->data != NULL)
  84.       FREE(texture->data);
  85.     old_texture = texture;
  86.     texture = texture->next;
  87.     FREE(old_texture);
  88.   }
  89.   csg_remove(object[csg->left], csg_removed, non_csg_removed);
  90.   object[csg->left] = NULL;
  91.   csg_remove(object[csg->right], csg_removed, non_csg_removed);
  92.   object[csg->right] = NULL;
  93.   FREE(rem_object->data);
  94.   FREE(rem_object);
  95.   POSINC(*csg_removed);
  96. }
  97.  
  98. void
  99. csg_normal(position, csg_object, normal)
  100.   xyz_ptr         position;
  101.   object_ptr      csg_object;
  102.   xyz_ptr         normal;
  103. {
  104.   REG int         i;
  105.   REG real        k;
  106.   xyz_struct      old_position, new_normal;
  107.   object_ptr      new_csg_object;
  108.   csg_ptr         csg;
  109.   int             transfs;
  110.   xyzw_ptr        transf[CSG_NODES_MAX];
  111.   xyz_ptr         transf_position[CSG_NODES_MAX];
  112.  
  113.   new_csg_object = csg_object;
  114.   csg = (csg_ptr) csg_object->data;
  115.   if (csg_object->transf != NULL)
  116.     STRUCT_ASSIGN(old_position, *(csg->position));
  117.   else
  118.     STRUCT_ASSIGN(old_position, *position);
  119.   transfs = 0;
  120.   csg_object->surface_id = csg->surface_id;
  121.   csg_object->refraction = csg->refraction;
  122.   csg_object->texture = csg->texture;
  123.   /* CSG transformations */
  124.   for (i = 0; i < (int) hit_global.data[0].tree.depth; POSINC(i))
  125.   {
  126.     if (RIGHT_TREE_PATH(i))
  127.       new_csg_object = object[csg->right];
  128.     else
  129.       new_csg_object = object[csg->left];
  130.     if (new_csg_object->object_type != CSG_TYPE)
  131.       break;
  132.     csg = (csg_ptr) (new_csg_object->data);
  133.     if ((csg_object->surface_id < 0) AND(csg->surface_id >= 0))
  134.       csg_object->surface_id = csg->surface_id;
  135.     if ((csg_object->refraction < 0.0) AND(csg->refraction > 0.0))
  136.       csg_object->refraction = csg->refraction;
  137.     if ((csg_object->texture == NULL) AND(csg->texture != NULL))
  138.       csg_object->texture = csg->texture;
  139.     if (new_csg_object->transf != NULL)
  140.     {
  141.       STRUCT_ASSIGN(old_position, *(csg->position));
  142.       transf[transfs] = new_csg_object->transf;
  143.       transf_position[transfs] = csg->position;
  144.       POSINC(transfs);
  145.     }
  146.   }
  147.   if (csg_object->surface_id < 0)
  148.     csg_object->surface_id = hit_global.data[0].object->surface_id;
  149.   if (csg_object->refraction < 0.0)
  150.     csg_object->refraction = hit_global.data[0].object->refraction;
  151.   if (csg_object->texture == NULL)
  152.     csg_object->texture = hit_global.data[0].object->texture;
  153.   OBJECT_NORMAL(&old_position, hit_global.data[0].object, normal);
  154.   /* CSG Normal inverse transformations */
  155.   while (transfs > 0)
  156.   {
  157.     POSDEC(transfs);
  158.     transform_normal_vector(transf[transfs], transf_position[transfs],
  159.                             normal, &new_normal);
  160.     STRUCT_ASSIGN(*normal, new_normal);
  161.     NORMALIZE(*normal);
  162.   }
  163.   if (csg_object->transf != NULL)
  164.   {
  165.     csg = (csg_ptr) csg_object->data;
  166.     transform_normal_vector(csg_object->transf, csg->position, normal,
  167.                             &new_normal);
  168.     STRUCT_ASSIGN(*normal, new_normal);
  169.     NORMALIZE(*normal);
  170.   }
  171.   k = DOT_PRODUCT(hit_global.data[0].vector, *normal);
  172.   if ((hit_global.data[0].enter == ENTERING) == (k > 0.0))
  173.   {
  174.     /* Flip normal */
  175.     normal->x = -normal->x;
  176.     normal->y = -normal->y;
  177.     normal->z = -normal->z;
  178.   }
  179. }
  180.  
  181. void
  182. csg_enclose(csg_object, csg_removed, non_csg_removed)
  183.   int             csg_object, *csg_removed, *non_csg_removed;
  184. {
  185.   xyz_struct      max, min, temp, vertex;
  186.   csg_ptr         csg;
  187.   object_ptr      parent, left, right;
  188.   xyz_struct      tmp;
  189.  
  190.   parent = object[csg_object];
  191.   csg = (csg_ptr) parent->data;
  192.   left = object[csg->left];
  193.   right = object[csg->right];
  194.   switch (csg->op)
  195.   {
  196.   case CSG_UNION:
  197.     if ((left == NULL) AND(right == NULL))
  198.     {
  199.       WRITE(results, "Warning: null CSG UNION (OBJECT %d)\n", csg_object);
  200.       csg_remove(parent, csg_removed, non_csg_removed);
  201.       object[csg_object] = NULL;
  202.       return;
  203.     }
  204.     if (right == NULL)
  205.     {
  206.       WRITE(results, "Warning: dummy CSG UNION (null RIGHT OBJECT %d)\n",
  207.             csg->right);
  208.       object[csg_object] = left;
  209.       object[csg->left] = NULL;
  210.       csg_remove(parent, csg_removed, non_csg_removed);
  211.       return;
  212.     }
  213.     if (left == NULL)
  214.     {
  215.       WRITE(results, "Warning: dummy CSG UNION (null LEFT OBJECT %d)\n",
  216.             csg->left);
  217.       object[csg_object] = right;
  218.       object[csg->right] = NULL;
  219.       csg_remove(parent, csg_removed, non_csg_removed);
  220.       return;
  221.     }
  222.     parent->min->x = MIN(left->min->x, right->min->x);
  223.     parent->min->y = MIN(left->min->y, right->min->y);
  224.     parent->min->z = MIN(left->min->z, right->min->z);
  225.     parent->max->x = MAX(left->max->x, right->max->x);
  226.     parent->max->y = MAX(left->max->y, right->max->y);
  227.     parent->max->z = MAX(left->max->z, right->max->z);
  228.     break;
  229.   case CSG_INTERSECTION:
  230.     if ((left == NULL) OR(right == NULL)
  231.         OR(left->max->x < right->min->x)
  232.     OR(left->min->x > right->max->x)
  233.         OR(left->max->y < right->min->y)
  234.     OR(left->min->y > right->max->y)
  235.         OR(left->max->z < right->min->z)
  236.     OR(left->min->z > right->max->z))
  237.     {
  238.       WRITE(results, "Warning: null CSG INTERSECTION (OBJECT %d)\n",
  239.         csg_object);
  240.       csg_remove(parent, csg_removed, non_csg_removed);
  241.       object[csg_object] = NULL;
  242.       return;
  243.     }
  244.     parent->min->x = MAX(left->min->x, right->min->x);
  245.     parent->min->y = MAX(left->min->y, right->min->y);
  246.     parent->min->z = MAX(left->min->z, right->min->z);
  247.     parent->max->x = MIN(left->max->x, right->max->x);
  248.     parent->max->y = MIN(left->max->y, right->max->y);
  249.     parent->max->z = MIN(left->max->z, right->max->z);
  250.     break;
  251.   case CSG_SUBTRACTION:
  252.     if (left == NULL)
  253.     {
  254.       WRITE(results, "Warning: null CSG SUBTRACTION (OBJECT %d)\n",
  255.         csg_object);
  256.       csg_remove(parent, csg_removed, non_csg_removed);
  257.       object[csg_object] = NULL;
  258.       return;
  259.     }
  260.     if ((right == NULL)
  261.         OR(left->max->x < right->min->x) OR(left->min->x > right->max->x)
  262.         OR(left->max->y < right->min->y) OR(left->min->y > right->max->y)
  263.         OR(left->max->z < right->min->z) OR(left->min->z > right->max->z))
  264.     {
  265.       WRITE(results, "Warning: dummy CSG SUBTRACTION (null RIGHT OBJECT %d)\n",
  266.             csg->right);
  267.       object[csg_object] = left;
  268.       object[csg->left] = NULL;
  269.       csg_remove(parent, csg_removed, non_csg_removed);
  270.       return;
  271.     }
  272.     parent->min->x = left->min->x;
  273.     parent->min->y = left->min->y;
  274.     parent->min->z = left->min->z;
  275.     parent->max->x = left->max->x;
  276.     parent->max->y = left->max->y;
  277.     parent->max->z = left->max->z;
  278.     break;
  279.   }
  280.   csg->surface_id = parent->surface_id;
  281.   csg->refraction = parent->refraction;
  282.   csg->texture = parent->texture;
  283.   if (parent->transf != NULL)
  284.   {
  285.     ALLOCATE(csg->position, xyz_struct, 1);
  286.     STRUCT_ASSIGN(max, *(parent->max));
  287.     STRUCT_ASSIGN(min, *(parent->min));
  288.     temp.x = min.x;
  289.     temp.y = min.y;
  290.     temp.z = min.z;
  291.     transform(parent->inv_transf, &temp, parent->min);
  292.     STRUCT_ASSIGN(*(parent->max), *(parent->min));
  293.     temp.x = min.x;
  294.     temp.y = min.y;
  295.     temp.z = max.z;
  296.     transform(parent->inv_transf, &temp, &vertex);
  297.     if (vertex.x < parent->min->x)
  298.       parent->min->x = vertex.x;
  299.     if (vertex.x > parent->max->x)
  300.       parent->max->x = vertex.x;
  301.     if (vertex.y < parent->min->y)
  302.       parent->min->y = vertex.y;
  303.     if (vertex.y > parent->max->y)
  304.       parent->max->y = vertex.y;
  305.     if (vertex.z < parent->min->z)
  306.       parent->min->z = vertex.z;
  307.     if (vertex.z > parent->max->z)
  308.       parent->max->z = vertex.z;
  309.     temp.x = min.x;
  310.     temp.y = max.y;
  311.     temp.z = min.z;
  312.     transform(parent->inv_transf, &temp, &vertex);
  313.     if (vertex.x < parent->min->x)
  314.       parent->min->x = vertex.x;
  315.     if (vertex.x > parent->max->x)
  316.       parent->max->x = vertex.x;
  317.     if (vertex.y < parent->min->y)
  318.       parent->min->y = vertex.y;
  319.     if (vertex.y > parent->max->y)
  320.       parent->max->y = vertex.y;
  321.     if (vertex.z < parent->min->z)
  322.       parent->min->z = vertex.z;
  323.     if (vertex.z > parent->max->z)
  324.       parent->max->z = vertex.z;
  325.     temp.x = min.x;
  326.     temp.y = max.y;
  327.     temp.z = max.z;
  328.     transform(parent->inv_transf, &temp, &vertex);
  329.     if (vertex.x < parent->min->x)
  330.       parent->min->x = vertex.x;
  331.     if (vertex.x > parent->max->x)
  332.       parent->max->x = vertex.x;
  333.     if (vertex.y < parent->min->y)
  334.       parent->min->y = vertex.y;
  335.     if (vertex.y > parent->max->y)
  336.       parent->max->y = vertex.y;
  337.     if (vertex.z < parent->min->z)
  338.       parent->min->z = vertex.z;
  339.     if (vertex.z > parent->max->z)
  340.       parent->max->z = vertex.z;
  341.     temp.x = max.x;
  342.     temp.y = min.y;
  343.     temp.z = min.z;
  344.     transform(parent->inv_transf, &temp, &vertex);
  345.     if (vertex.x < parent->min->x)
  346.       parent->min->x = vertex.x;
  347.     if (vertex.x > parent->max->x)
  348.       parent->max->x = vertex.x;
  349.     if (vertex.y < parent->min->y)
  350.       parent->min->y = vertex.y;
  351.     if (vertex.y > parent->max->y)
  352.       parent->max->y = vertex.y;
  353.     if (vertex.z < parent->min->z)
  354.       parent->min->z = vertex.z;
  355.     if (vertex.z > parent->max->z)
  356.       parent->max->z = vertex.z;
  357.     temp.x = max.x;
  358.     temp.y = min.y;
  359.     temp.z = max.z;
  360.     transform(parent->inv_transf, &temp, &vertex);
  361.     if (vertex.x < parent->min->x)
  362.       parent->min->x = vertex.x;
  363.     if (vertex.x > parent->max->x)
  364.       parent->max->x = vertex.x;
  365.     if (vertex.y < parent->min->y)
  366.       parent->min->y = vertex.y;
  367.     if (vertex.y > parent->max->y)
  368.       parent->max->y = vertex.y;
  369.     if (vertex.z < parent->min->z)
  370.       parent->min->z = vertex.z;
  371.     if (vertex.z > parent->max->z)
  372.       parent->max->z = vertex.z;
  373.     temp.x = max.x;
  374.     temp.y = max.y;
  375.     temp.z = min.z;
  376.     transform(parent->inv_transf, &temp, &vertex);
  377.     if (vertex.x < parent->min->x)
  378.       parent->min->x = vertex.x;
  379.     if (vertex.x > parent->max->x)
  380.       parent->max->x = vertex.x;
  381.     if (vertex.y < parent->min->y)
  382.       parent->min->y = vertex.y;
  383.     if (vertex.y > parent->max->y)
  384.       parent->max->y = vertex.y;
  385.     if (vertex.z < parent->min->z)
  386.       parent->min->z = vertex.z;
  387.     if (vertex.z > parent->max->z)
  388.       parent->max->z = vertex.z;
  389.     temp.x = max.x;
  390.     temp.y = max.y;
  391.     temp.z = max.z;
  392.     transform(parent->inv_transf, &temp, &vertex);
  393.     if (vertex.x < parent->min->x)
  394.       parent->min->x = vertex.x;
  395.     if (vertex.x > parent->max->x)
  396.       parent->max->x = vertex.x;
  397.     if (vertex.y < parent->min->y)
  398.       parent->min->y = vertex.y;
  399.     if (vertex.y > parent->max->y)
  400.       parent->max->y = vertex.y;
  401.     if (vertex.z < parent->min->z)
  402.       parent->min->z = vertex.z;
  403.     if (vertex.z > parent->max->z)
  404.       parent->max->z = vertex.z;
  405.   }
  406. }
  407.